\documentclass{ctexart}
\bibliographystyle{IEEEtran}
\usepackage{booktabs}
\usepackage{url}
\usepackage{algorithm,algorithmic,amsmath,amsthm,amssymb,amsfonts}
\usepackage{listings,graphics}
\usepackage{xcolor}
\usepackage{tikz}
\pagestyle{plain}
\title{AvlTree的特定输出}
\author{张祺\\信息与计算科学 2101  3210104145}
\date{2022年10月28日}
\begin{document}
\maketitle
\section{设计思路}
通过二分迭代的方式，先找到距离$K_1$最近的key值并将其输出，返回上一级后输出第二小的key，由此不断将堆砌的栈释放，每次都输出最小的root值，以此来达到输出所有key的目的。\par
注：修改了部分AvlTree.h文件内容。
\section{理论分析}
通过代码，我们可以将整个函数分为两个部分：一是不断的迭代过程，二是将得到的key值输出。\par
因此$T(n)=T_1(n)+T_2(n)$,且$T_2(n)=O(K)$。(K为输出key值的总数）\par
  $\because$ $T_1(n)=T_1(n/2)$+t,t is const int\par
  $\therefore$ while considering $T_1(n)$,we just see t as 1.\par
  Also, with the Master Method (B):if $f(n)=\Theta(n^{\log_{b}{a}})$, then $T(n)=\Theta(n^{\log_{b}{a}}\log{n});$\par
  $\therefore$ $the T_1(n)=\Theta(\log{n})=O(\log{n})$\par
  $\therefore$ $T(n)=O(K+\log{n})$\par
\section{测试说明}
\subsection{样例说明}
共有三组样例，第一组是保持k1-k2不变，选取多个N值观察T(N)的变化;第二组是保持N不变，选取多个k1、k2值观察T(N)的变化;第三组是保持N不变，改变k1、k2的位置观察对T(N)是否有影响。
\subsection{结果分析}
\subsubsection{第一组}
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|} \hline
  (k1-k2, N) & (50, 100) & (50, 1000) & (50, 10000) & (50, 100000) & (50, 1000000) \\ \hline
  time & 6.4e-05 & 0.000229 & 0.002096 & 0.03243 & 0.3015 \\ \hline
  (k1-k2, N) & (50, 2000000) & (50, 4000000) & (50, 6000000) & (50, 8000000) & (50, 10000000) \\ \hline
  time & 0.6138 & 1.25 & 1.60 & 2.52 & 2.63 \\ \hline
\end{tabular}
\end{center}
\begin{figure}[h]
  \centerline{\includegraphics[width=0.5\linewidth]{图片1.png}}
\end{figure}
保持K不变，T(N)的变化与理论分析较符合，按照$c(K+\log{n})$的方式增长。
\subsubsection{第二组}
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|} \hline
   (k1-k2, N) & (10, 1000000) & (100, 1000000) & (1000, 100000) & (10000, 100000) & (100000, 1000000) \\ \hline
  time & 0.301 & 0.303 & 0.304 & 0.32 & 0.56\\ \hline
\end{tabular}
\end{center}
保持N不变，T(N)的变化与理论分析较符合，也是按照$c(K+\log{n})$的方式增长。
\subsubsection{第二组}
\begin{center}
\begin{tabular}{|c|c|c|c|c|c|} \hline
   (k1, k2, N) & (523788, 524788, 1000000) & (1, 1001, 1000000) & (999000, 1000000, 100000) \\ \hline
  time & 0.48 & 0.304258 & 0.278678 \\ \hline
\end{tabular}
\end{center}
当k1、k2分别在root的两端时，程序需要花费更多的时间;而当k1、k2同属一侧时，程序效率较快。
\end{document}
